干货 | 基于红黑树的高效IP归属地查询方案
邢钦华，携程风控团队高级研发经理。2016年加入携程，是风控大数据平台Chloro的设计和开发的主要参与者。专注于大数据流式处理和用户行为分析在互联网风控领域中的应用。
在实时风控系统中会涉及到非常多的数据衍生和解析，比如IP归属地解析、手机号归属地解析、银行卡卡BIN解析等等。以IP归属地为例，传统的实现IP归属地查询的方法是把IP地址信息存储到关系型数据库中，对于并发量比较少，实时性要求不高的情况下是可行的，但是一旦并发量增大时，会对关系型数据库产生很大的压力，并且访问速度会明显减慢，因此对于高并发、实时性要求高的场合这种查询方法就显得力不从心。
本文我们将以IP归属地为例，介绍一下携程风控是如何实现相对静态数据的高效衍生的。我们会把IP归属地信息保存到内存中，经过一系列的转变，最终形成红黑树，利用红黑树高效的查找性能，实现了高效的IP归属地解析方案，该方案可承担较大的并发访问压力，并拥有极低的响应延时。
实现方案：
图1
如图1所示，首先把IP地址信息录入到数据库中，系统把已经录入好的IP地址信息从数据库中读取到计算机内存，经过一系列的索引形式的转换，把最终的索引以及把IP地址转成long形式的整数后存放到计算机内存中的红黑树中，当有访问请求获取IP的归属地信息时，首先把具体的IP地址转成long形式的整数，根据此证书到红黑树中查询到其对应的结点，获取该结点的索引数据，再根据该索引数据获取到IP归属地信息，并且返回给用户。
图2
如图2所示为IP地址分类图，在TCP/IP协议中，IP地址以二进制数字的形式出现，总共4个字节，即32个bit，由网络编号（N-ID）和主机编号（H-ID）组成。根据网络地址的不同，IP地址可以分为五类： A类地址、B类地址、C类地址、D类地址以及E类地址。
对于同一个物理网络上的计算机主机，其网络编号是相同的，不同的是主机编号。在为各个城市分配IP地址时，通常是把多个连续的IP地址段分配给某一城市，例如：1.12.0.0 到1.12.255.255，1.15.168.0到1.15.191.255等连续的IP地址段都属于北京的IP地址。通常每个城市包含了多个连续的IP地址段，在这些IP地址段中的IP地址都属于该城市的IP地址，由于IP是有4个字节组成的，并且没有负数，可以把IP地址段转成两个8字节的long类型整数，在这两个整数之间的数字都属于该城市的IP地址。
IP地址是由4段组成的，如1.15.168.0，其对应的4字节二进制形式为00000001.00001111.10101000.00000000，根据计算机的计算特性，可以把第一段左移24位、第二段左移16位、第三段左移8位、第四段不移动，得到整数相加就是IP地址转换后的整数值，即16777216 + 983040 + 43008 + 0 =17803264。
图3
图4
红黑树是一种非常成熟的数据结构，是每个结点都带有红色或者黑色的二叉查找树，是比较高效的，可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。红黑树在满足二叉查找树的要求外，还必须满足一下要求：
1、节点是红色或黑色。
2、根是黑色。
3、所有叶子都是黑色（叶子是NIL节点）。
4、每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路
径上不能有两个连续的红色节点。）
5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
JSON是一中数据格式，主要用于数据交换，易于人阅读和编写，同时也易于计算机解析和生成。
本系统中，IP地址的归属地信息包含了国家（country）、地区（region）、市（city）等属性。
首先把IP地址信息从数据库中以JSON格式读取到计算机内存中，例如：
{"region":"天津","start":"1.15.232.0","end":"1.15.232.255","city":"天津","country":"中国"}，
{"region":"辽宁","start":"1.14.33.0","end":"1.14.33.255","city":"大连","country":"中国"}，
{"region":"北京","start":"1.15.186.0","end":"1.15.186.255","city":"北京","country":"中国"}，
{"region":"北京","start":"1.12.27.0","end":"1.12.27.255","city":"北京","country":"中国"}，
其中start为数据该城市连续IP段的起始IP，end为结束IP。
然后把这些IP归属地信息封装成Area类的集合。Area类由type和name字段组成，其中name表示一个国家或者地区或者城市的名称，比如上面的IP地址信息中的中国、天津、北京、辽宁和大连。type是由country、region、city单独或者任意相加组成，其中country、region、city分别用1、2、4表示，这样当type为1时表示一个国家，为2时表示一个省，为4时表示一个城市，为3时表示国家名和地区名相同，为5时表示国家名和城市名相同，为7时表示国家、地区、城市的名称相同。转换后的数据如下所示：
表1
type | name |
1 | 中国 |
6 | 天津 |
2 | 辽宁 |
4 | 大连 |
6 | 北京 |
然后再把上面的Area类的集合数据转成raw-meta数据，其中index位Area类的集合的索引。
表2
type | name | index |
1 | 中国 | 0 |
6 | 天津 | 1 |
2 | 辽宁 | 2 |
4 | 大连 | 3 |
6 | 北京 | 4 |
然后再根据IP地址信息和表2中的raw-meta数据转换成fomatted-raw-ip数据，其中国家索引为IP地址信息中country字段对应的表2中index列的相应值，地区索引为region字段对应的表2中index列的相应值，城市索引为city字段对应的表2中index列的相应值。
表3
国家索引 | 地区索引 | 城市索引 | 开始IP | 结束IP |
0 | 1 | 1 | 1.15.232.0 | 1.15.232.255 |
0 | 2 | 3 | 1.14.33.0 | 1.14.33.255 |
0 | 4 | 4 | 1.15.186.0 | 1.15.186.255 |
0 | 4 | 4 | 1.12.27.0 | 1.12.27.255 |
进一步，表3中第3、4行的国家索引、地区索引，城市索引是相同，都是国家为中国，地区为北京，城市为北京，为了消除重复数据，再把fomatted-raw-ip数据转换为segment-regions-ip数据。
表4
国家索引 | 地区索引 | 城市索引 | fomatted-raw-ip索引 |
0 | 1 | 1 | 0 |
0 | 2 | 3 | 1 |
0 | 4 | 4 | 2 |
然后再把IP归属地信息和segment-regions-ip数据转为compact-ex-ip-segment数据，其中第一行为segment-regions-ip的索引。
表5
segment-regions-ip的索引 | 开始IP | 结束IP |
0 | 1.15.232.0 | 1.15.232.255 |
1 | 1.14.33.0 | 1.14.33.255 |
2 | 1.12.27.0 | 1.12.27.255 |
2 | 1.15.186.0 | 1.15.186.255 |
表5的IP地址转换成long整数。
表6
segment-regions-ip的索引 | 开始IP | 结束IP |
0 | 17819648 | 17819903 |
1 | 17703168 | 17703423 |
2 | 17570560 | 17570815 |
2 | 17807872 | 17808127 |
最后把compact-ex-ip-segment转成红黑树保存在计算机内存中，每个红黑树结点由parent，left，right，color，from，end，index组成。parent 为父节点，left为左结点 right为右结点，color 表示该结点为红色或者黑色，from为起始IP转成的long整数，end为结束IP转成的long整数，index为compact-ex-ip-segment数据保存的索引，即表6的第一次列。
由于红黑树中存放的是IP段的起始IP转换后的整数和结束IP转换后的整数，而需要查询的是具体IP地址转换后的整数，因此查询的规则是：先把IP转换为整数，从红黑树的root结点开始查起，当该整数小于结点中的from整数时，继续沿着红黑树该结点的左边查找，当该整数大于结点中的end整数时，继续沿着红黑树中该结点的右边查找，否则，该查找到的结点即为要查找的IP信息对应的结点。
若查找过程中，结点为NIL节点，说明该IP地址不是有效的IP。例如IP地址为1.15.186.10，首先把IP转成long型的整数，即17807882。然后去红黑树中查找该整数对应的红黑树中的结点为2，17807872，17808127，进而取到索引2，即segment-regions-ip的索引，根据表4取到数据0,4,4,2，其中2为fomatted-raw-ip集合的索引，0,4,4为raw-meta数据的最后一列，即为Area类集合的索引，从而找到country为0，即中国，region为4，即北京，city为4即北京。因此该IP对应的国家为中国、地区为北京、城市为北京。
当红黑树形成以后，在具体IP查询过程中，从数据库中读取的IP地址信息的JSON格式数据已经不再需要，可以从内存中删除。最终留在内存中的数据为Area类的集合，segment-regions-ip数据，红黑树，这样就可以减少计算机内存的使用。经统计，本系统中IP地址信息的总条数为719296，经过对系统启动前后，计算机内存的比较，系统启动后共占用了大约20兆（MB）的内存，在现在计算机技术快速发展的时代，一般家用的计算机的内存也有2千兆（GB）或者更多，公司专门的服务器的内存甚至高达几十GB，因此这些数据的内存占用量可以说是微不足道的。
当IP地址信息的条数增加时，只需要以目前的格式添加到数据库中，然后重启应用程序即可，当需要更详细的IP地址信息时，比如经纬度、运营供应商，除了在数据库中添加相应信息外，只需要增加Area类的相应信息的字段，重启应用程序即可，因此，此系统具有良好的扩展性。
该方案不仅适用于IP归属地查询，也适用于其他相对静态的数据的快速解析。
【职位推荐】
简历投递邮箱：tech@ctrip.com
邮件标题：【应聘职位】+姓名
数据挖掘工程师，上海
岗位职责：
1、根据公司业务需求，针对业务数据完成各个纬度的统计与分析。
2、深度挖掘用户数据、建立用户画像、设计风险评估模型，控制支付风险。
3、配合开发人员完成数据模型开发、上线运行
任职要求：
1、数学、统计学、金融、计算机等专业。
2、熟练掌握oracle、mysql等关系型数据库，能够自主完成数据提取与分析。
3、熟悉python等数据分析常用软件。
4、熟悉决策树、逻辑回归、聚类、判别分析、因子分析等常用数据挖掘算法和统计分析方法。
5、极强的责任心、学习能力、沟通协作能力。
Java高级开发经理，上海
岗位职责：
1、分析业务需求，将需求拆分为独立的业务功能；
2、分配研发任务，监督设计与实现过程，保证产物按时按量完成；
3、负责部分核心系统设计、研发与优化工作，协助解决项目研发过程中的技术难题；
4、对具体开发人员进行技术指导，协助推进规范与标准的落实；
任职要求:
1、计算机相关专业，本科及以上学历；
2、五年以上java及WEB应用软件开发经验，二年以上系统设计经验，并熟知软件开发流程，熟悉敏捷开发流程，有敏捷团队的实际管理经验。有消费金融业务系统研发经验优先；
3、 精通jJava，多线程编程，消息系统，数据库，分布式调用等技术，对SOA的模式有较深的理解，对Linux下的开发环境有 较深厚的开发经验；
4、熟悉maven项目配置管理工具，熟悉tomcat. jboss等应用服务器，同时对在高并发处理情况下的负载调优有相关经验者优先考虑；
5、熟悉网络编程，具有设计和开发对外API接口经验和能力，同时具备跨平台的API规范设计以及API高效调用设计能力者优先考虑；
6、具有良好的沟通. 团队协作. 计划和创新的能力。
【荐号】携程风控
专注于互联网风险管理，分享最前沿风控技术。
想了解风险管理如何为业务保驾护航吗？在这里都可以找到答案。
携程风控定时推送一线技术文章，欢迎关注！
【推荐阅读】